package week01

// 304. 二维区域和检索 - 矩阵不可变
// https://leetcode-cn.com/problems/range-sum-query-2d-immutable/

type NumMatrix struct {
	sums [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	var m, n = len(matrix)+1, len(matrix[0])+1

	sums := make([][]int, m)
	sums[0] = make([]int, n)
	for i := 1; i < len(sums); i++ {
		sums[i] = make([]int, n)
		for j := 1; j < len(sums[i]); j++ {
			sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + matrix[i-1][j-1]
		}
	}
	return NumMatrix{
		sums: sums,
	}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	return this.sums[row2+1][col2+1] - this.sums[row1][col2+1] - this.sums[row2+1][col1] + this.sums[row1][col1]
}
